package org.basis.algorithm.list;

import org.basis.algorithm.list.common.ListNodeUtil;
import org.basis.algorithm.list.common.SingleNode;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 链表排序，主要是通过两种方式：
 * 1、通过将链表节点加入到数组中，然后对数组进行排序
 * 2、将链表节点加入到优先队列里，利用优先队列小根堆的特性
 *
 * @author Mr_wenpan@163.com 2021/12/09 11:12
 */
public class ListSort {

    public static void main(String[] args) {
        SingleNode<Integer> singleNode = ListNodeUtil.generateIntegerSingleList(20, 20, false);
//        SingleNode<Integer> head = listSortByPriorityQueue(singleNode);
        SingleNode<Integer> head = listSortByArray(singleNode);
        ListNodeUtil.printSingleList(head);
    }

    private static SingleNode<Integer> listSortByArray(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        int len = 0;
        SingleNode<Integer> p = head;
        while (p != null) {
            len++;
            p = p.next;
        }
        SingleNode<Integer>[] arr = new SingleNode[len];
        for (int i = 0; i < len; i++) {
            arr[i] = head;
            head = head.next;
        }
        Arrays.sort(arr, (o1, o2) -> {
            return o1.data - o2.data;
        });

        SingleNode<Integer> q = arr[0];
        // 将节点串联起来
        for (int i = 1; i < arr.length; i++) {
            q.next = arr[i];
            q = q.next;
        }
        // 最后一个节点的next指针置空
        arr[arr.length - 1].next = null;

        return arr[0];
    }

    private static SingleNode<Integer> listSortByPriorityQueue(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        PriorityQueue<SingleNode<Integer>> queue = new PriorityQueue<>((o1, o2) -> {
            return o1.data - o2.data;
        });
        while (head != null) {
            queue.add(head);
            head = head.next;
        }
        SingleNode<Integer> newHead = queue.poll();
        SingleNode<Integer> q = newHead;
        while (!queue.isEmpty()) {
            // 这里
            q.next = queue.poll();
            q = q.next;
        }
        // 尾部节点置空
        if (null != q) {
            q.next = null;
        }
        return newHead;
    }
}
